package graph;

import java.util.*;

public class Solution_207 {
    public boolean canFinish0(int numCourses, int[][] prerequisites) {
        Map<int[], Integer> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            int x = prerequisite[0], y = prerequisite[1];
            if (map.containsKey(new int[]{y, x}))
                return false;
            else {
                map.put(prerequisite, 1);
            }
        }
        return true;
    }

    /**
     * 只能处理直接成环的问题，无法处理间接的，比如：[0,1],[1,2],[2,0]
     */
    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        Set<String> seen = new HashSet<>();
        for (int[] p : prerequisites) {
            int x = p[0], y = p[1];
            String reverse = y + "," + x;
            if (seen.contains(reverse) || x == y) {
                return false;
            }
            seen.add(x + "," + y);
        }
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();

        for (int[] p : prerequisites) {
            int cur = p[0], pre = p[1];
            graph[pre].add(cur);          // pre -> cur
            inDegree[cur]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) q.offer(i);
        }

        int finished = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            finished++;
            for (int v : graph[u]) {
                if (--inDegree[v] == 0) q.offer(v);
            }
        }
        return finished == numCourses;
    }


    public static void main(String[] args) {
        Solution_207 solution207 = new Solution_207();
        System.out.println(solution207.canFinish(2, new int[][]{{1, 0}, {0, 1}}));
    }
}
